package 中等.贪心思想;

/**
 * 给你一个字符串 s ，它每一位都是 1 到 9 之间的数字组成，同时给你一个整数 k 。
 * 如果一个字符串 s 的分割满足以下条件，我们称它是一个 好 分割：
 * s 中每个数位 恰好 属于一个子字符串。
 * 每个子字符串的值都小于等于 k 。
 * 请你返回 s 所有的 好 分割中，子字符串的 最少 数目。如果不存在 s 的 好 分割，返回 -1 。
 * 注意：
 * 一个字符串的 值 是这个字符串对应的整数。比方说，"123" 的值为 123 ，"1" 的值是 1 。
 * 子字符串 是字符串中一段连续的字符序列。
 *  
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/partition-string-into-substrings-with-values-at-most-k
 */
public class 将字符串分割成值不超过K的子字符串_6196 {

    public static void main(String[] args) {

        System.out.println(minimumPartition("165462"
                , 60));

    }

    /**
     * 从索引 0 开始尝试分割，尽量多分割一些数字
     */
    public static int minimumPartition(String s, int k) {
        int count = 0, idx = 0;
        while (idx < s.length()) {
            if (s.charAt(idx) - '0' > k) {
                return -1;
            }
            long num = 0;
            while (idx < s.length() && num * 10 + s.charAt(idx) - '0' <= k) {
                num *= 10;
                num += s.charAt(idx) - '0';
                idx++;
            }
            count++;
        }

        return count;
    }

}
